package 基数排序;

import java.util.Arrays;

public class 基数排序 {
	public static void main(String[] args) {
		int[] arr = {51,32,43,23,15};
		radixSort(arr);
		System.out.println(Arrays.toString(arr));
		
		
//		int[] longInt = new int[80000];
//		for (int i = 0; i < longInt.length; i++) {
//			longInt[i] = (int) (Math.random()*10000);
//		}
//		
//		long star = System.currentTimeMillis();
//		radixSort(longInt);
//		long end = System.currentTimeMillis();
//		System.out.println((end-star) + "毫秒");		//29 ms  
//		System.out.println((end-star)/1000 + "秒");//0s
	}
	
	//可以处理正负
	public static void radixSort(int[] arr) {
		
		//找出长位数的数字，不分正负
		int max = arr[0];
		for(int i = 1 ; i < arr.length ; i++) {
			if(Math.abs(arr[i]) > max) {
				max = arr[i];
			}
		}
		//如果最长是负数，先变正数
		if(max < 0) {
			max = -max;
		}
		//Integer :max.toString().length();
		int maxlength = (max + "").length();
		
		//定义10个桶，每个桶里能放数据
		//定义19个桶，每个桶里能放数据，前0-8放负数，9放0，后10-19放正数
		//bucket[]=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]
		//bucket[]=[-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9]
		int[][] bucket = new int[19][arr.length];
		//定义桶记录，记录每个桶里有几个数据，遍历用，因为每个位数占一位，所以共有10个位置
		//定义桶记录，记录每个桶里有几个数据，遍历用，正负都有，所以共有19个位置
		int[] countnum = new int[19];
		
		//y 用来取出当前位数
		for(int i = 0, y = 1; i < maxlength ; i++, y = y * 10) {
			
			//开始循环原始数组
			for(int num : arr) {
				//取出当前位数
				int digit = num / y % 10;
				//要区分正负所以+9，正数放后面，负数放前面
				//bucket[]=[-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9]
				digit = digit + 9;
				//存到桶里，桶记录代表当前桶里有几个了，要把当前数字存到第几个位置。
				bucket[digit][countnum[digit]] = num;
				//桶记录加1，存一次就把这个位数加一个记录，代表上一个数已经被占了，指向下一个数，等着
				//上面这句countnum[digit]取出来是0，值与digit无关，digit只是下标
				countnum[digit]++;
			}
		
			//取完一遍之后，将桶里数字取出，放到原始数组中
			//index表示原始数组下标
			int index = 0;
			//有几个桶，就遍历几次，实际有数的桶可以用桶记录长度
			for(int m = 0 ; m < countnum.length; m++) {
				//去每一个桶里找数据，countnum[i] 每个位置上的数表示，桶里有几个数据，有数就进去找
				if(countnum[m] != 0) {
					for(int n = 0 ; n < countnum[m] ; n++) {
						
						arr[index] = bucket[m][n];
						index++;
					}
				}
				
				//取出数据之后，桶记录没用了，清零
				countnum[m] = 0;
			}
		}
		
		
		
	}
}
